package com.xcrj.test;

public class Test8 {
    public long combinationSum4(int[] nums, int target) {
        // dp[组成目标i]=方法数
        long[] dp = new long[target + 1];
        dp[0] = 1;// dp[组成目标0]=什么也不放也是1个方法
        // 排列问题，先背包再物品
        for (int i = 1; i < target + 1; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                    if (dp[i] == Long.MAX_VALUE) {
                        System.out.println(i);
                        return -1;
                    }
                    if (i == 649) {
                        System.out.println("i = 649, dp[i] = " + dp[i]);
                    }
                    if (i == 650) {
                        System.out.println("i = 650, dp[i] = " + dp[i]);
                        break;
                    }
                }
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        int[] nums = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210,
                220,
                230, 240, 250, 260, 270, 280, 290, 300, 310, 320, 330, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430,
                440,
                450, 460, 470, 480, 490, 500, 510, 520, 530, 540, 550, 560, 570, 580, 590, 600, 610, 620, 630, 640, 650,
                660,
                670, 680, 690, 700, 710, 720, 730, 740, 750, 760, 770, 780, 790, 800, 810, 820, 830, 840, 850, 860, 870,
                880,
                890, 900, 910, 920, 930, 940, 950, 960, 970, 980, 990, 111 };
        int target = 999;
        Test8 main2 = new Test8();
        long ans = main2.combinationSum4(nums, target);
        System.out.println(ans);
    }
}
